Modem computer program languages are based on modular design models, where computer code is written in small, modular units or subprograms that define certain objects or functions. These subprograms may be called (i.e. invoked) wherever desired in the program by a simple reference to the subprogram. While modular program design is an effective programming technique, additional overhead may be introduced during the execution stage after the program is compiled. An overhead penalty is introduced when a subprogram is called frequently but the execution time of the subprogram is small relative to the time required to call the subprogram.
Most compilers are equipped with various optimization routines that determine how to represent the original source code in an efficient executable form, such as reducing the size and required execution time of various calls to the subprogram. One well known optimization technique is referred to as inlining. Inlining techniques replace the subprogram calls at the various locations in the computer program with the lines of code that define the subprogram. Inlining is typically performed when a subprogram is called many times in a program and when the execution time of the subprogram is small compared with the time necessary to set-up for and call the subprogram.
Inlining provides performance improvements for various reasons. First, the subprogram linkage is removed, including the code to save and restore registers, allocate stack space, and the branch itself. Second, the code surrounding the call site can be improved, since the call itself, which may be a barrier for some optimization procedures, is no longer present. By removing the call site, it is also possible to perform better instruction scheduling, register allocation, etc. Third, the subprogram code that is substituted for the call can be optimized for the specific call context.
The decision to inline a subprogram may be determined by the compiler automatically or assisted by user directed inlining. With user directed inlining, the programmer specifies which subprograms should be inlined. The compiler then attempts to inline the subprograms chosen by the user at each of its call sites. When automatic inlining is used, the compiler determines which subprograms should be inlined by following a set of inline optimization rules. However, the typical rules implemented by a compiler do not account for subprograms that exhibit varying execution characteristics due to the range of variables or arguments over which the subprogram operates. With the varying arguments, the subprogram's actual run-time may be substantially influenced depending on the argument received. For example, within a subprogram various execution paths may be taken based on the argument received. In some cases, the path taken is shorter and faster than others and the path may be taken more frequently. However, because subprograms are inlined based on the execution time of the subprogram as a whole, the disparate execution times and disparate frequency of execution of the different paths are not accounted for very well in optimization techniques.
One method used to help the compiler determine whether to inline based on different variables is referred to as profiling. When using profiling, the computer program is executed at compile time using different data scenarios to determine how programs will perform (profiling) before producing the final compiled code. The use of profiling information typically requires at least two passes to compile the program. One pass is performed then the compiled program is executed to generate the profiling information, and the other pass performs the automatic inlining based on the profiling information. The compiler's determination of whether to inline a subprogram that has been profiled is typically based on the number of times a subprogram is called and the execution time of the subprogram. While using profiling to determine whether to inline a subprogram is beneficial in some cases, it does not solve the optimization problem introduced by subprograms that exhibit significantly different execution or run-time characteristics based on the arguments used or execution paths taken in the subprograms. That is, profiling only provides a guess as to the best way to inline based on the data sets used to perform the profiling. Hence, the compiler's decision whether to inline may be correct or efficient for some scenarios but costly for others.
Thus, there is a need for a system and method that enables a compiler to make inlining decisions that are efficient for subprograms that have significantly varying execution times over a range of variables or execution paths.